深入 next、字符串处理(头疼）
题目 动物园
思路分析
气到了 学不来
看似简单 本来是因为求的是最长不公共前后缀长度 发现是数量
对这个cnt实在理解不了 模拟了半天 也还是不行
题目逻辑
- KMP算法的next数组：KMP算法中的next数组用于记录字符串的每个位置之前的子串中，最长的相等的前缀和后缀的长度。例如，在字符串"abcababc"中，
next[5] = 2意味着前5个字符"abcab"中，最长的相同前后缀是"ab"，长度为2。 - num数组的定义：题目要求求出一个num数组，对于字符串S的前i个字符构成的子串，num[i]表示既是它的后缀同时又是它的前缀，并且这个后缀与这个前缀不重叠的字符串的数量。这是一个对KMP算法的扩展应用。
- 求解方法：通过修改KMP算法来实现。在计算next数组的同时，利用next数组来计算每个前缀的非重叠前后缀的数量。最后，将所有前缀的非重叠前后缀数量加一后的值相乘，并对1,000,000,007取模得到最终答案。
代码解析
代码中的关键步骤如下：
- 初始化：对每个测试用例，首先读入字符串，并初始化
cnt[1] = 1，因为第一个字符没有前后缀。 - 计算next数组和cnt数组：通过一个循环计算next数组和cnt数组。对于字符串的每一个字符，如果当前字符与它前面的某个前缀的下一个字符相同，则更新next值。同时，利用next数组来更新cnt数组，
cnt[i] = cnt[ne[i]] + 1，这里的+1表示包括当前字符本身作为一个长度为1的前后缀。 - 计算结果：初始化一个变量
ans = 1，遍历字符串的每一个位置，利用next数组和cnt数组计算每个位置的贡献，即((LL)cnt[j] + 1) % M，然后将这些值累乘得到最终结果。 - 输出结果：对每个测试用例，输出计算得到的结果模1,000,000,007。
逻辑和实现的挑战
- 理解KMP算法：需要深入理解KMP算法，尤其是next数组的计算方法和含义。
- 扩展应用：在KMP算法的基础上进行扩展，引入num数组的概念，并计算所有前缀的非重叠前后缀数量的乘积。
- 精确处理边界条件：精确处理字符串的每一个位置，尤其是在处理前缀和后缀不重叠的逻辑时。
核心
cnt数组的求解
cnt数组的目的是为了记录对于字符串S的每一个前缀，满足既是它的后缀又是它的前缀，并且这个后缀与这个前缀不重叠的字符串的数量加一。这里加一是因为考虑到每个前缀本身至少有一个不重叠的前后缀（即它自身）。
- 初始化：对于字符串的第一个字符，它没有前后缀，所以
cnt[1]初始化为1。 - 计算过程：从字符串的第二个字符开始计算每个位置的
cnt值。这个计算依赖于ne数组，它记录了字符串每个位置之前的子串中，最长的相等的前缀和后缀的长度。在计算cnt[i]时，我们查看ne[i]的值，即当前位置i的最长相等前后缀的长度，并将cnt[ne[i]] + 1作为cnt[i]的值。
- 为什么是
cnt[ne[i]] + 1：这里的思路是，对于位置i的子串，其最长的相等前后缀已经由ne[i]给出，而cnt[ne[i]]记录了这个最长前后缀对应的不重叠前后缀的数量。因为我们在考虑位置i的子串时，除了这个最长的前后缀外，i本身可能代表一个新的不重叠前后缀的开始（特别是对于重复字符的情况），所以我们需要加1。
ans的求解
最终答案ans是通过将所有cnt数组中的值（每个值都加1）相乘，再对1,000,000,007取模得到的。这里，加1是因为cnt数组中的值已经考虑了至少一个不重叠的前后缀（即本身），所以直接用于乘积计算。
- 初始化：
ans初始化为1，这是乘积操作的标准初始化值。 - 计算过程：遍历字符串的每一个位置i。对于每个位置i，我们需要确定不重叠前后缀的数量。由于
cnt数组已经记录了包含当前字符的不重叠前后缀数量加一的值，我们直接使用cnt[j] + 1（这里j是根据KMP算法调整的，以确保不考虑重叠的前后缀）。
- 重要的一步：在乘以
cnt[j] + 1之前，我们需要确保考虑的前后缀不会导致重叠。这通过检查j * 2 > i来实现。如果j * 2 > i，则说明当前的最长前后缀导致重叠，需要通过回溯ne[j]来找到一个不重叠的前后缀。
- 乘积并取模：对于每个位置i的
cnt[j] + 1，将其乘入ans中，并在每步中对1,000,000,007取模，以避免整数溢出。 - 输出结果：遍历完成后，
ans就是所有不重叠前后缀数量加一的乘积对1,000,000,007取模的结果。
代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 1e9 + 7;
int ne[N], cnt[N]; //cnt数组存储每个位置的不重叠前后缀数量加一
char sc[N];
int main() {
int t;
scanf("%d", &t);
while (t--)
{
scanf("%s", sc + 1);
int n = strlen(sc + 1);
cnt[1] = 1; // 字符串的第一个字符没有前后缀，所以初始值为1（只有字符本身）
for (int i = 2, j = 0; i <= n; i++)
{
while (j && sc[i] != sc[j + 1])
j = ne[j];
if (sc[i] == sc[j + 1])
j++;
ne[i] = j;
/*
对于每个位置i，cnt[i]的值是cnt[ne[i]]+1。
这里，ne[i]表示前i个字符构成的子串的最长前后缀的长度，
cnt[ne[i]]表示这个最长前后缀对应的不重叠前后缀的数量，
加1是因为考虑到S[i]本身也可以是一个单独的不重叠前后缀。
*/
cnt[i] = cnt[ne[i]] + 1;//加一是在加上它本身，因为它本身相等也是允许的
}
LL ans = 1; // 初始化结果为1
for (int i = 1, j = 0; i <= n; i++) {
while (j && sc[i] != sc[j + 1])
j = ne[j];
if (sc[i] == sc[j + 1])
j++;
/*
对于字符串S的某个位置i，要确保一个前后缀不重叠，前后缀的长度必须小于等于i的一半，
因为如果前后缀长度大于i的一半，那么前后缀必然重叠。
换句话说，如果最长前后缀的长度j满足j * 2 > i，则说明前后缀重叠
*/
while (j && (j * 2 > i))
j = ne[j]; // 如果前后缀重叠，则回溯到上一个匹配位置
// 计算最终答案，cnt[j]表示不重叠前后缀的数量，加1是考虑到字符串本身
ans = ans * ((LL)cnt[j] + 1) % M;
}
cout << ans % M << endl; // 输出结果
}
return 0;
}
同类题型
视频讲解
⬅️ 拓展 循环结问题(头疼警告） 🏠 00-刷题理模型 ➡️ 串相关模型
💬 评论